package com.sise.Tree;

import com.sise.Linked.ListNode;

/**
 *      109. 有序链表转换二叉搜索树
 *
 *      给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
 *      本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
 *
 *      题解：
 *          依旧需要使用快慢指针找到中点，根据中点的值创建 root 节点，接着传递 left，right 给左右子树
 */
public class _109_sortedListToBST {
    public TreeNode sortedListToBST(ListNode head) {
        return build(head, null);
    }

    private TreeNode build(ListNode left, ListNode right){
        if (left == right) return null;

        ListNode mid = getMid(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = build(left, mid);
        root.right = build(mid.next, right);
        return root;
    }

    // 对于链表的寻找中点，可以使用快慢指针。同时这里需要传递 right，一开始传递的为 null，因为 null 是链表的最终节点，
    // 后续拆分左右子树，那么 right 就很有必要，找 left - right 的中点
    private ListNode getMid(ListNode left, ListNode right){
        ListNode slow = left;
        ListNode fast = left;
        while (fast != right && fast.next != right){        // 注意这里使用的是 while
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
